package com.example.design.leetcode.dynamic;

//剑指 Offer 10 - I. 斐波那契数列
//    写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。
//    斐波那契数列的定义如下：
//    F(0) = 0, (1) = 1
//    F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
//    斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
//
//    答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
//
//    示例 1：
//    输入：n = 2
//    输出：1
//
//    示例 2：
//    输入：n = 5
//    输出：5
//
//    提示：
//    0 <= n <= 100

public class Practice41 {
    /**
     * F(n)表示为斐波那契数列中第n个数字
     * 转移方程：F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
     * 边界条件： F[0] = 0, F[1] = 1 ，因为在计算 n+1 时需要 2 个元素，所以要初始化 2 个值；
     * @param n
     * @return
     */
    public int fib(int n) {
        int n1 = 0;
        int n2 = 1;
        int sum;

        for (int i = 0; i < n; i++) {
            sum = (n1 + n2)%1000000007;
            n1 = n2;
            n2 = sum;
        }

        return n1;
    }

}
